package leetCode;

import java.util.HashMap;

public class PartitionArrayforMaximumSum {
    public int maxSumAfterPartitioning(int[] A, int K) {
        HashMap<String, int[]> dp = new HashMap<>();
        int N = A.length;
        dp.put(toStr(0, 1), new int[]{A[0], A[0]});
        for (int i = 1; i < N; i++) {
            int max = 0;
            for (int j = 1; j <= K && j <= i; j++) {
                max = Math.max(max, dp.get(toStr(i - 1, j))[1]);
            }
            dp.put(toStr(i, 1), new int[]{A[i], max + A[i]});
            for (int j = 2; j <= K && j <= i + 1; j++) {
                int oldMax = dp.get(toStr(i - 1, j - 1))[0];
                int newMax = Math.max(oldMax, A[i]);
                int newSum = dp.get(toStr(i - 1, j - 1))[1];
                if (oldMax == newMax) {
                    newSum += oldMax;
                } else {
                    newSum -= oldMax * (j - 1);
                    newSum += newMax * j;
                }
                dp.put(toStr(i, j), new int[]{newMax, newSum});
            }
        }
        int res = 0;
        for (int i = 1; i <= K; i++) {
            res = Math.max(res, dp.get(toStr(N - 1, i))[1]);
        }

        return res;
    }

    private String toStr(int i, int i1) {
        return i + "_" + i1;
    }
}
